package Dynamic_programming;

import java.util.Arrays;

/**
 * @Description: $
 * @Param: $
 * @return: $
 * @Author 万家欣
 * @Date: 2022/7/21
 * Algorithm
 * @Version 1.0
 */
public class CommDao {
    //冒泡排序：通过两两比较将需要的数交换（若由大到小则当arr[i] <arr[i +1}时交换，反之亦然。），由于每一次排序都会确定最后的数必定在其对应位置。因此j<arrays.length-1-i为内层循环
    public void BubbleSort(int[] arrays) {
        for (int i = 0; i < arrays.length - 1; i++) {

            //            控制比较次数,三者交换，实现排序
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                if (arrays[j] > arrays[j + 1]) {
                    int temp = 0;//类似空桶
                    temp = arrays[j]; //A桶中水倒入空桶C中
                    arrays[j] = arrays[j + 1];//把B桶的水倒入A桶中
                    arrays[j + 1] = temp;//把C桶的水倒入B桶中
                }
            }
        }
        System.out.println(Arrays.toString(arrays));
    }

    //快速排序
    public void QuickSort(int[] arrays) {
        sort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
        ;
    }

    //快速排序的具体实现（通过递归实现）
    public void sort(int[] arrays, int left, int right) {
        int l = left;
        int r = right;

        int pivot = arrays[(left + right) / 2];
        int temp = 0;
        while (l < r) {

            //在左边查找小于中间值的
            while (arrays[l] < pivot) {
                l++;
            }
            //查询右边小于中间值
            while (arrays[r] > pivot) {
                r--;
            }
            if (l >= r) {
                break;
            }
            temp = arrays[l];
            arrays[l] = arrays[r];
            arrays[r] = temp;

//            交换完数据arrays[l] = pivot
            if (arrays[l] == pivot) {
                r--;
            }
            if (arrays[r] == pivot) {
                l++;
            }
            if (r == l) {
                l++;
                r--;
            }
            if (left < r) {
                sort(arrays, left, r);
            }
            if (right > l) {
                sort(arrays, l, right);
            }
        }
    }

    //基数排序：
    //     1.获取原序列的最大位多少
    //      @param arrays
    public void BasicSort(int[] arrays) {

        //        获取最大位数
        int max = 0;
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] > max) {
                max = arrays[i];
            }
        }

        //        获取字符串长度，所以把int类型转字符串类型
        int maxLength = (max + "").length();

        //      定义二维数组，大小10，表示10个桶，每一个桶则是一个数组
        //       [[],[],[],[],[]...]
        int[][] bucket = new int[10][arrays.length];

        //        辅助数组
        int[] bucketElementCount = new int[10];

        //        循环获取无序数列
        for (int j = 0; j < arrays.length; j++) {
            int locationElement = arrays[j] % 10;

            //            放入桶中
            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

        //        遍历每一个桶，讲元素存放原数组中
        int index = 0;
        for (int k = 0; k < bucketElementCount.length; k++) {
            if (bucketElementCount[k] != 0) {
                for (int l = 0; l < bucketElementCount[k]; l++) {
                    arrays[index++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }
        System.out.println(Arrays.toString(arrays));

        //        第一轮针对个位数进行比较
        for (int j = 0; j < arrays.length; j++) {
            int locationElement = arrays[j] / 1 % 10;

            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

        //        取出来按照桶的顺序放回原数组中
        int indx = 0;
        for (int k = 0; k < bucketElementCount.length; k++) {
            if (bucketElementCount[k] != 0) {
                for (int l = 0; l < bucketElementCount[k]; l++) {
                    arrays[indx++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }

        //        判断十位数
        for (int j = 0; j < arrays.length; j++) {
            int locationElement = arrays[j] / 10 % 10;

            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

        //        取出来按照桶的顺序放回原数组中
        indx = 0;
        for (int k = 0; k < bucketElementCount.length; k++) {
            if (bucketElementCount[k] != 0) {
                for (int l = 0; l < bucketElementCount[k]; l++) {
                    arrays[indx++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }

        //        获取百位数比较
        for (int j = 0; j < arrays.length; j++) {
            int locationElement = arrays[j] / 100 % 10;

            bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
            bucketElementCount[locationElement]++;
        }

//        取出来按照桶的顺序放回原数组中
        indx = 0;
        for (int k = 0; k < bucketElementCount.length; k++) {
            if (bucketElementCount[k] != 0) {
                for (int l = 0; l < bucketElementCount[k]; l++) {
                    arrays[indx++] = bucket[k][l];
                }
            }
            bucketElementCount[k] = 0;
        }
        System.out.println("基数排序后的顺序:" + Arrays.toString(arrays));
    }

    //插入排序
    public void InsertSort(int[] array) {
        //控制拿去每一个元素
        for (int i = 1; i < array.length; i++) {
            //比较次数
            for (int j = i; j >= 1; j--) {
                //是否小于前面的元素
                if (array[j] < array[j - 1]) {
                    int temp = 0;
                    temp = array[j];
                    array[j] = array[j - 1];
                    array[j - 1] = temp;
                } else {
                    //continue 与 break
                    break;
                }
            }
        }
        System.out.println("排序后的结果：" + Arrays.toString(array));
    }

    //选择排序
    public void SelectSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {

            for (int j = arr.length - 1; j > i; j--) {

                if (arr[j] < arr[i]) {

                    int temp = 0;
                    temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
        System.out.println("选择排序后的结果:" + Arrays.toString(arr));
    }

    //希尔排序
    public void ShellSort(int[] array) {
        //        实现增量变化
        for (int gap = array.length / 2; gap > 0; gap /= 2) {

            for (int i = gap; i < array.length; i++) {

                for (int j = i - gap; j >= 0; j -= gap) {
                    if (array[j] > array[j + gap]) {
                        int temp = 0;
                        temp = array[j];
                        array[j] = array[j + gap];
                        array[j + gap] = temp;
                    }
                }
            }
        }
        System.out.println(Arrays.toString(array));
    }

    //归并排序
    public void MSort(int[] array) {
        //临时数组
        int[] temp = new int[array.length];
        mSort(array, 0, array.length - 1, temp);
    }

    //归并排序具体实现：将数组分为左右归并：
    public void mSort(int[] array, int left, int right, int[] temp) {
        if (left < right) {

            //            求出中间值
            int mid = (left + right) / 2;

            //            向左边分解
            mSort(array, left, mid, temp);
            //            向右边分解
            mSort(array, mid + 1, right, temp);
            //            合并数据
            sum(array, left, right, mid, temp);
        }
    }

    /**
     * 归并排序合并元素
     *
     * @param array
     * @param left
     * @param right
     * @param mid
     * @param temp
     */
    public static void sum(int[] array, int left, int right, int mid, int[] temp) {
        int i = left;
        int j = mid + 1;

        //        指向临时数组下标
        int t = 0;

        //        开始循环比较左右两遍数组元素比较
        while (i <= mid && j <= right) {

            if (array[i] <= array[j]) {
                temp[t] = array[i];
                t++;
                i++;
            } else {
                temp[t] = array[j];
                t++;
                j++;
            }
        }

        //        把剩余的元素直接存放在临时数组中
        while (i <= mid) {
            temp[t] = array[i];
            t++;
            i++;
        }
        while (j <= right) {
            temp[t] = array[j];
            t++;
            j++;
        }

        //        临时数组中的元素拷贝至原数组中
        int tempIndex = left;
        int k = 0;
        while (tempIndex <= right) {
            array[tempIndex] = temp[k];
            k++;
            tempIndex++;
        }
    }

    //计数排序
    public void countSort(int[] a) {
        int b[] = countSort1(a);
        for (int i : b) {
            System.out.print(i + ",");
        }
    }

    //计数排序的具体实现：
    public int[] countSort1(int[] a) {
        int b[] = new int[a.length];
        int max = a[0], min = a[0];
        for (int i : a) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }//这里k的大小是要排序的数组中，元素大小的极值差+1
        int k = max - min + 1;
        int c[] = new int[k];
        for (int i = 0; i < a.length; ++i) {
            c[a[i] - min] += 1;//优化过的地方，减小了数组c的大小
        }
        for (int i = 1; i < c.length; ++i) {
            c[i] = c[i] + c[i - 1];
        }
        for (int i = a.length - 1; i >= 0; --i) {
            b[--c[a[i] - min]] = a[i];//按存取的方式取出c的元素
        }
        return b;
    }

    //堆排序
    public static int[] heapSort(int[] array) {
        //这里元素的索引是从0开始的,所以最后一个非叶子结点array.length/2 - 1
        for (int i = array.length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, array.length);  //调整堆
        }

        // 上述逻辑，建堆结束
        // 下面，开始排序逻辑
        for (int j = array.length - 1; j > 0; j--) {
            // 元素交换,作用是去掉大顶堆
            // 把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置
            swap(array, 0, j);
            // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。
            // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因
            // 而这里，实质上是自上而下，自左向右进行调整的
            adjustHeap(array, 0, j);
        }
        return array;
    }

    /**
     * 整个堆排序最关键的地方
     *
     * @param array  待组堆
     * @param i      起始结点
     * @param length 堆的长度
     */
    public static void adjustHeap(int[] array, int i, int length) {
        // 先把当前元素取出来，因为当前元素可能要一直移动
        int temp = array[i];
        for (int k = 2 * i + 1; k < length; k = 2 * k + 1) {  //2*i+1为左子树i的左子树(因为i是从0开始的),2*k+1为k的左子树
            // 让k先指向子节点中最大的节点
            if (k + 1 < length && array[k] < array[k + 1]) {  //如果有右子树,并且右子树大于左子树
                k++;
            }
            //如果发现结点(左右子结点)大于根结点，则进行值的交换
            if (array[k] > temp) {
                swap(array, i, k);
                // 如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，循环对子节点所在的树继续进行判断
                i = k;
            } else {  //不用交换，直接终止循环
                break;
            }
        }
    }

    /**
     * 交换元素
     *
     * @param arr
     * @param a   元素的下标
     * @param b   元素的下标
     */
    public static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    //桶排序
    public static void basket(int data[])//data为待排序数组
    {
        int n = data.length;
        int bask[][] = new int[10][n];
        int index[] = new int[10];
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            max = max > (Integer.toString(data[i]).length()) ? max : (Integer.toString(data[i]).length());
        }
        String str;
        for (int i = max - 1; i >= 0; i--) {
            for (int j = 0; j < n; j++) {
                str = "";
                if (Integer.toString(data[j]).length() < max) {
                    for (int k = 0; k < max - Integer.toString(data[j]).length(); k++){
                        str += "0";
                    }
                }
                str += Integer.toString(data[j]);
                bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = data[j];
            }
            int pos = 0;
            for (int j = 0; j < 10; j++) {
                for (int k = 0; k < index[j]; k++) {
                    data[pos++] = bask[j][k];
                }
            }
            for (int x = 0; x < 10; x++) {
                index[x] = 0;
            }
        }
    }

}
